The invention relates generally to electrical computers and digital processing systems, and more particularly to test pattern generators.
Known automatic test pattern generation (xe2x80x9cATPGxe2x80x9d) methods activate a fault at a site, attempt to propagate the fault to an output, then work backward through the circuit in an effort to xe2x80x9cjustifyxe2x80x9d signal levels needed to activate and propagate the fault (see for example Roth, J. P., xe2x80x9cDiagnosis of automata failures: A calculus and a method,xe2x80x9d IBM J. Res.Dev. 10:278-281, 1966).
The U.S. Pat. No. 4,204,633 to Goel, issued May 27, 1980, teaches a method that avoids the need for backward justification. However, when signal assignment conflicts arise, previous decisions are systematically reversed until an input combination is found that makes the fault detectable at an output. When a fault has no test or few tests, considerable time may be consumed in a sometimes-fruitless search for a conflict-free input assignment.
A preferred embodiment of the present invention defines a method for generating all tests for all detectable faults during a single pass through a sorted definition of a combinational circuit. Such a method avoids the conditional behavior of many currently used methods.
The method provides a netlist defining a combinational circuit in terms of interconnected primary inputs, logic elements, and primary outputs. The netlist is sorted into an ascending circuit-level order commencing at the level of the primary inputs. Data structures are defined for a fault, a fault-propagation function, and a path-enabling function. A library of Boolean function combining rules is provided for each of the logic element types present in the circuit definition. Initial data structures are created for each of the primary inputs.
The rules are applied to the data structures that form the inputs to each circuit level to create and store data structures that will form the inputs to the next circuit level, commencing at the level of the primary inputs, and progressing through the circuit definition circuit-level-by-circuit-level.
In the preferred embodiment an attempt is made to activate and propagate all faults to primary outputs during a single pass through the circuit definition. Each fault reaching a primary output is a detectable fault. The fault-propagation function for each detectable fault defines all primary input assignments that permit the fault to be activated and propagated to the primary output. These input assignments define all tests for the detectable fault.
The computational effort of creating the path-enabling functions is shared among all faults during the single pass, thus reducing the overall effort. The preferred path-enabling function is the 1-set.
In another embodiment, the invention defines methods that release no-longer-needed data structure storage, permitting the handling of larger circuits. In yet another embodiment, the invention defines methods that stop propagating faults once they reach a primary output, thereby reducing overall computational effort.